#include <assert.h>

using namespace std;

namespace lty{
    template <class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;

        vector()
        {}

        vector(size_t n,const T& val=T())
        {
            reserve(n);
            for(size_t i=0;i<n;i++)
            {
                push_back(val);
            }
        }

        // [first, last) 左必右开区间
        template <class InputIterator>
        vector(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        //v2(v1)深拷贝
//        vector(const vector<T>& v)
//        {
//            _start = new T[v.capacity()];
//            //memcpy(_start, v._start, sizeof(T)*v.size());//浅拷贝
//            for (size_t i = 0; i < v.size(); ++i)
//            {
//                _start[i] = v._start[i];//当vector<vector<int>>时，是一个二维数组，没写赋值重载，是一个浅拷贝，需要再写赋值重载
//            }
//
//            _finish = _start + v.size();
//            _end_of_storage = _start + v.capacity();
//        }

        vector(const vector<T>& v)
        {
            vector<T> tmp(v.begin(),v.end());//借助迭代器拷贝来把v中的数据全部拷贝进tmp中
            swap(tmp);//tmp和this交换数据即可实现二维v2(v1)深拷贝
        }

        vector<T>& operator=(vector<T> v)
        {
            swap(v);//this和形参v交换，交换后的v因为是形参所以不会改变
            return *this;
        }

        void swap(vector<T> &v)
        {
            std::swap(_start,v._start);
            std::swap(_finish,v._finish);
            std::swap(_end_of_storage,v._end_of_storage);
        }
        ~vector()
        {
            delete[] _start;
            _start=_finish=_end_of_storage= nullptr;
        }

        iterator begin()
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }
        const_iterator begin() const
        {
            return _start;
        }
        const_iterator end() const
        {
            return _finish;
        }

        void resize(size_t n,T val=T())
        {
            if(n<size())
            {
                _finish=_start+n;//删除数据
            }
            else
            {
                if(n>capacity())
                    reserve(n);
                while(_finish!=_start+n)//如果_finish不在末尾，初始化后面的空间为val值
                {
                    *_finish=val;
                    ++_finish;
                }
            }
        }
        void reserve(size_t n)
        {
            if(n>capacity())//判断是否缩容
            {
                size_t sz=size();//储存扩容前的size大小
                T* tmp=new T[n];
                if(_start)//如果不为空
                {
//                    memcpy(tmp,_start,sizeof(T)*size());/当vector中的类型是string时是浅拷贝
                    for (size_t i = 0; i < sz; ++i)
                    {
                        tmp[i]=_start[i];
                    }
                    delete[] _start;
                }
                _start=tmp;//此时_start地址已改变，如果直接用size()，会导致_finish位置出错
                _finish=_start + sz;
           // _finish=_start + size();//_finish - _start 抵消剩_finish,且size()为负数
                _end_of_storage=_start+n;
            }
        }
        void push_back(const T& x)
        {
            if(_finish==_end_of_storage)
            {
//        this->reserve(capacity()== 0 ? 4 : capacity()*2);
                reserve(capacity()== 0 ? 4 : capacity()*2);//this调用扩容
            }
            *_finish=x;
            ++_finish;
        }

        void pop()//尾删
        {
            assert(!empty());
            --_finish;
        }

        void insert(iterator pos,const T& val)
        {
            assert(pos>=_start);
            assert(pos<=_finish);//可以在_finish处插入
            if(_finish==_end_of_storage)//检查容量避免while越界移动数组
            {
                size_t len=pos-_start;//记录pos和_start的相对距离
                //如果扩容，扩容后的_start地址改变，迭代器pos地址还是以前的地址，迭代器失效
                reserve(capacity()== 0 ? 4 : capacity()*2);
                pos=_start+len;//更新pos位置 解决pos迭代器失效   tips：pos还是一个指针类型的形参，这里改变，外面不改变且失效
            }
            iterator end=_finish-1;//_finish的位置是null值
            while(end>=pos)
            {
                *(end+1)=*end;//移动数组
                --end;
            }
            *pos=val;//pos位置插入val
            ++_finish;
        }

        iterator erase(iterator pos)
        {
            assert(pos<_finish);//_finish处没有元素不能删除
            assert(pos>=_start);
            iterator start=pos+1;
            while(start!=_finish)//数据前移
            {
                *(start-1)=*start;
                ++start;
            }
            --_finish;//删除最后一个数据
            return pos;//返回pos值以便外部继续使用迭代器，解决迭代器失效问题
        }

        size_t capacity() const
        {
            return _end_of_storage-_start;
        }
        size_t size() const
        {
            return _finish-_start;
        }

        T& operator[](size_t pos)
        {
            assert(pos<size());
            return _start[pos];
        }
        const T& operator[](size_t pos) const//函数重载 给const类型用
        {
            assert(pos<size());
            return _start[pos];
        }

        bool empty()//判断是否为空
        {
            return _start==_finish;
        }
    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;


    };



    void Print(const vector<int> v)
    {
//        for(size_t i=0;i<v.size();++i)
//        {
//            cout << v[i] << " ";
//        }
//        cout << endl;
//        auto it=v.begin();
//        while(it<v.end())
//        {
//            cout << *it << " ";
//            ++it;
//        }
//        cout << endl;
        for(auto a:v)
        {
            cout << a << " ";
        }
        cout << endl;
    }

    //测试
    void test1()//push_back尾插+resize
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        v1.push_back(5);
        Print(v1);
        v1.resize(10);
        Print(v1);
    }
    void test2()
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        v1.push_back(5);
        auto pos=find(v1.begin(),v1.end(),3);//区间找3
        if(pos!=v1.end())
        {
            v1.insert(pos,333);//pos位置插入333
        }
        //严格来说pos用过后失效了，不能再使用
        //(*pos)++;
        Print(v1);
        pos= find(v1.begin(),v1.end(),333);
        v1.erase(pos);
        //erase后也失效，不要访问，行为结果未定义(和编译器有关)
        Print(v1);
    }
    void test3()//迭代器更新，解决迭代器pos失效问题
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        v1.push_back(5);
        auto it = v1.begin();
        while (it != v1.end())
        {
            if (*it % 2 == 0)
            {
                it = v1.erase(it);
            }
            else
            {
                ++it;
            }
        }
        Print(v1);
    }
    void test4()
    {

    }
}





